package projects;

import java.util.ArrayList;
import java.util.Random;


public class Clustering {
	
	public static void main(final String[] args) {		
		Clustering cluster = new Clustering();
		cluster.run(args);
	}
	
	private void run(final String[] args) {
		try {
			String fileName = args[0];
			String algorithm = args[1];
			
			System.out.println("arff file: " + fileName);	
			System.out.println("algorithm: " + algorithm);
			
			boolean removeIDColumn = args[2].equals("removeIDColumn") ? true : false;
			boolean removeLabelColumn = args[3].equals("removeLabelColumn") ? true : false;
			if (removeIDColumn) System.out.println("removeIDColumn");
			if (removeLabelColumn) System.out.println("removeLabelColumn");
			
			features = initMatrix(fileName, removeIDColumn, removeLabelColumn);
			System.out.println("# instances: " + features.rows());
			
			if (args[args.length - 1].equals("-N")) {
				features.normalize();
				System.out.println("Using normalized data");
			}
			
			ClusterGroup[] clusters = null;			
			if (algorithm.equals("hac")) {
				Link link = args[4].equals("single") ? Link.SINGLE : Link.COMPLETE;
				System.out.println("link: " + link.toString());
				int kStart = Integer.parseInt(args[5]);
				int kEnd = Integer.parseInt(args[6]);
				System.out.println("k-range: " + kStart + "-" + kEnd);
				clusters = computeHAC(features, link, kStart, kEnd);
				printOutputData(clusters, kStart, kEnd);
			}
			else if (algorithm.equals("kmeans")) {
				int k = Integer.parseInt(args[4]);
				System.out.println("k: " + k);
				boolean random = (args[5].equals("random"))? true : false;		
				if (random) {
					System.out.println("Using random centroids");
					clusters = computeKMeans(features, k, new Random());
				}
				else					
					clusters = computeKMeans(features, k, null);
				printOutputData(clusters, k, k);
			}
			
		}
		catch (Exception e) { e.printStackTrace(); }		
	}
	
	public void printOutputData(final ClusterGroup[] clusters, 
			final int kStart, final int kEnd) {		
		
		for (int k = kStart; k <= kEnd; k++) {
			
			System.out.println("\n\n\n----------------------------------------" +
					"---------------------------------------------------");
			ClusterGroup clusterGroup = clusters[k];
			if (clusters[k] == null) continue;
			
			// Number of clusters
			System.out.println("Number of clusters = " + clusters[k].size() + "\n");
			
			int numInstances = 0;
			double totalSSE = 0;
			for (Cluster cluster : clusterGroup) {
				numInstances += cluster.size();
				
				// Centroid values for each cluster
				System.out.println("Centroid " + 
						clusterGroup.indexOf(cluster) + " = " + cluster.computeCentroid());
				
				// # instances tied to that cluster
				System.out.println("# tied to Centroid = " + cluster.size());
				
				// SSE of each cluster
				double sse = sumSquaredError(cluster);
				System.out.println("SSE = " + sse + "\n");
				totalSSE += sse;
			}
			assert(numInstances == features.rows());
			
			// total SSE
			System.out.println("Total SSE for Clusters k=" + k + ": " + totalSSE);
			
			System.out.println("----------------------------------------" +
					"---------------------------------------------------");
		}
	}
	
	private Matrix initMatrix(final String fileName, 
			final boolean removeIDColumn, final boolean removeLabelColumn) throws Exception {
		Matrix data = new Matrix();
		data.loadArff(fileName);
		int colStart = 0;
		int colCount = data.cols();
		if (removeIDColumn)	colStart = 1;
		if (removeLabelColumn) colCount = data.cols() - 1;
		return new Matrix(data, 0, colStart, data.rows(), colCount - colStart);
	}	
	
	/**
	 * Creates an adjacency matrix based on a matrix of features
	 * (This disregards the label class)
	 */
	private void initAdjacencyMatrix(final Matrix features) {
		adjacencyMatrix = new Matrix();
		adjacencyMatrix.setSize(features.rows(), features.rows());
		for (int row = 0; row < features.rows(); row++) {
			for (int col = 0; col < features.rows(); col++) {
				double[] vector1 = features.row(row);
				double[] vector2 = features.row(col);
				double distance = distance(vector1, vector2);
				adjacencyMatrix.set(row, col, distance);
			}
		}	
	}
	
	private ClusterGroup initOneRowClusters(final Matrix features) {
		ClusterGroup clusterGroup = new ClusterGroup();
		for (int i = 0; i < features.rows(); i++) {
			Cluster oneRowCluster = new Cluster(i);
			clusterGroup.add(oneRowCluster);
		} 
		return clusterGroup;
	}

	/**
	 * K-Means Cluster
	 */					
	private ClusterGroup[] computeKMeans(final Matrix features, final int k, final Random rand) {
		CentroidGroup centroids = new CentroidGroup();
		ClusterGroup clusters = new ClusterGroup();	
		
		// Choose the first k instances from the data set as the initial centroids
		for (int i = 0; i < k; i++) {
			if (rand == null)
				centroids.add(new Centroid(features.row(i)));	
			else
				centroids.add(new Centroid(features.row(rand.nextInt(features.rows()))));
		}
		
		double oldSSE, newSSE;
		int i = 0;
		do {
			oldSSE = 0; newSSE = 0;
			for (Cluster cluster : clusters)
				oldSSE += sumSquaredError(cluster);
			clusters = groupIntoClusters(features, centroids);
			centroids.clear();
			for (Cluster cluster : clusters)
				centroids.add(cluster.computeCentroid());
			for (Cluster cluster : clusters)
				newSSE += sumSquaredError(cluster);
			
		} 
		while(improving(oldSSE, newSSE) || i++ < 3);
		
		ClusterGroup[] clusterGroups = new ClusterGroup[k+1];
		clusterGroups[k] = clusters;
		System.out.println("r" + k + ": " + r(clusters));
		return clusterGroups;
	}
	
	private ClusterGroup groupIntoClusters(final Matrix features, 
			final CentroidGroup centroids) {
		ClusterGroup clusters = new ClusterGroup(centroids.size());
		for (int r = 0; r < features.rows(); r++) {
			Centroid closestCentroid = closestCentroid(features.row(r), centroids);
			Cluster closestCluster = clusters.get(centroids.indexOf(closestCentroid));
			closestCluster.add(r);
		}
		return clusters;
	}
		
	private Centroid closestCentroid(final double[] row, final CentroidGroup centroids) {
		double leastDistance = Double.MAX_VALUE;
		Centroid closestCentroid = null;
		for (Centroid centroid : centroids)
			if (distanceFromCentroid(row, centroid) < leastDistance) {
				leastDistance = distanceFromCentroid(row, centroid);
				closestCentroid = centroid;
			}
		return closestCentroid;
	}
	
	
	private boolean improving(final double oldSSE, final double newSSE) {
		return Math.abs(oldSSE - newSSE) > .001;
	}

	/**
	 * Hierarchical Agglomerative Cluster
	 */
	private ClusterGroup[] computeHAC(final Matrix features, 
			final Link link, final int kStart, final int kEnd) {
		initAdjacencyMatrix(features);
		
		// clustersOfSizeK[0] will always be null
		ClusterGroup[] clustersOfSizeK = new ClusterGroup[features.rows() + 1];
		
		ClusterGroup clusterGroup = initOneRowClusters(features);
		clustersOfSizeK[features.rows()] = clusterGroup;		
		
		for (int k = features.rows() - 1; k >= 1; k--) {			
			ClusterGroup oldClusterGroup = new ClusterGroup(clusterGroup);			
			clusterGroup = new ClusterGroup();
			int[] indices = nearest2ClusterIndices(oldClusterGroup, link);
			
			Cluster cluster0 = oldClusterGroup.get(indices[0]);
			Cluster cluster1 = new Cluster(oldClusterGroup.get(indices[1]));
			cluster0.addAll(cluster1);			
			
			for (int i = 0; i < oldClusterGroup.size(); i++) 
				if (i != indices[1])
					clusterGroup.add(new Cluster(oldClusterGroup.get(i)));
			
			clustersOfSizeK[k] = clusterGroup; 
			assert(clustersOfSizeK[k].size() == k);
		}
		for (int k = kStart; k <= kEnd; k++)
			System.out.println("r" + k + ": " + r(clustersOfSizeK[k]));
		System.out.println("bestRIndex: " + bestRIndex(clustersOfSizeK, kStart, kEnd));
		return clustersOfSizeK;
	}
			
	/**
	 * Returns the nearest 2 clusters within an array of clusters 
	 * (each cluster represented as a matrix)
	 */
	private int[] nearest2ClusterIndices(final ClusterGroup clusterGroup, final Link link) {
		int[] nearest2Clusters = new int[2];
		double leastDistance = Double.MAX_VALUE;
		for (Cluster thisCluster : clusterGroup) {
			for (Cluster thatCluster : clusterGroup) {
				if (thisCluster.equals(thatCluster)) continue;
				if (clusterDistance(thisCluster, thatCluster, link) < leastDistance) {
					leastDistance = clusterDistance(thisCluster, thatCluster, link);
					nearest2Clusters[0] = clusterGroup.indexOf(thisCluster);
					nearest2Clusters[1] = clusterGroup.indexOf(thatCluster);
				}
			}
		}
		return nearest2Clusters;
	}
	
	private double clusterDistance(final Cluster thisCluster, 
			final Cluster thatCluster, final Link link) {
		double distance = (link == Link.SINGLE)? Double.MAX_VALUE : Double.MIN_VALUE;
		for (int thisRow : thisCluster)
			for (int thatRow : thatCluster)
				if ((link == Link.SINGLE && adjacencyMatrix.get(thisRow, thatRow) < distance) ||
					(link == Link.COMPLETE && adjacencyMatrix.get(thisRow, thatRow) > distance))
					distance = adjacencyMatrix.get(thisRow, thatRow);
		return distance;
	}
	
	private double centroidDistance(final Centroid centroid1, final Centroid centroid2) {
		double[] vector1 = new double[centroid1.size()];
		double[] vector2 = new double[centroid2.size()];
		for (int i = 0; i < centroid1.size(); i++) {
			vector1[i] = centroid1.get(i);
			vector2[i] = centroid2.get(i);
		}
		return distance(vector1, vector2);
	}
	
	/**
	 * Calculates Euclidean distances
	 * Nominal values have a distance of 0 for a match, else 1
	 * Unknown values have a distance of 1
	 */
	private double distance(final double[] vector1, final double[] vector2) {
		double sum = 0;
		for (int i = 0; i < vector1.length; i++) {
			if (vector1[i] == UNKNOWN || vector2[i] == UNKNOWN)
				sum += 1;
			else if (attributeIsNominal(i) && vector1[i] != vector2[i])
				sum += 1;
			else if (attributeIsNominal(i) && vector1[i] == vector2[i])
				sum += 0;
			else 
				sum += Math.pow(vector1[i] - vector2[i], 2);
		}
		return Math.sqrt(sum);
	}
	
	private double distanceFromCentroid(final double[] vector1, final Centroid centroid) {
		double[] vector2 = primitiveDoubleArray(centroid.toArray(new Double[centroid.size()]));
		return distance(vector1, vector2);
	}
		
	private double[] primitiveDoubleArray(final Double[] array) {
		double[] doubleArray = new double[array.length];
		for (int i = 0; i < array.length; i++)
			doubleArray[i] = array[i];
		return doubleArray;
	}
	
	private int bestRIndex(final ClusterGroup[] clustersOfSizeK,
			final int kStart, final int kEnd) {
		ArrayList<Double> rValues = new ArrayList<Double>();
		rValues.add(Double.MAX_VALUE); // Gets rid of index 0
		for (int k = 1; k < clustersOfSizeK.length; k++)
			rValues.add(r(clustersOfSizeK[k]));
		return rValues.indexOf(minValue(rValues, kStart, kEnd));
	}
	
	private double r(final ClusterGroup clusterGroup) {
		double sum = 0;
		for (Cluster i : clusterGroup) {
			ArrayList<Double> rValues = new ArrayList<Double>();
			for (Cluster j : clusterGroup) {
				if (i.equals(j)) continue;
				double distance = centroidDistance(i.computeCentroid(), j.computeCentroid());
				if (distance == 0)
					rValues.add(Double.MAX_VALUE);
				else
					rValues.add((scatter(i) + scatter(j)) / distance);
			}
			sum += maxValue(rValues);
		}
		return sum / clusterGroup.size();
	}
		
	private double maxValue(final ArrayList<Double> values) {
		double maxValue = Double.MIN_VALUE;
		for (double value : values)
			if (value > maxValue)
				maxValue = value;
		return maxValue;
	}
	
	private double minValue(final ArrayList<Double> values, 
			final int kStart, final int kEnd) {
		double minValue = Double.MAX_VALUE;
		for (int i = kStart; i <= kEnd; i++)
			if (values.get(i) < minValue)
				minValue = values.get(i);
		return minValue;
	}
	
	private double scatter(final Cluster cluster) {
//		return sumSquaredError(cluster) / cluster.size();
		return absValueError(cluster) / cluster.size();
	}
	
	private double absValueError(final Cluster cluster) {
		Centroid centroid = cluster.computeCentroid();
		double error = 0;
		for (int rowNum : cluster) {
			double distance = distanceFromCentroid(features.row(rowNum), centroid);
			error += Math.abs(distance);
		}
		return error;		
	}

	private double sumSquaredError(final Cluster cluster) {
		Centroid centroid = cluster.computeCentroid();
		double sumSquaredError = 0;
		for (int rowNum : cluster) {
			double distance = distanceFromCentroid(features.row(rowNum), centroid);
			sumSquaredError += Math.pow(distance, 2);
		}
		return sumSquaredError;
	}
	
	private boolean attributeIsNominal(final int col) {
		return features.valueCount(col) != 0;
	}

	
	@SuppressWarnings("serial")
	private class ClusterGroup extends ArrayList<Cluster> { 
		public ClusterGroup() {
			super();
		}
		public ClusterGroup(ClusterGroup that) {
			super(that);
			for (int i = 0; i < size(); i++)
				set(i, new Cluster(get(i)));				
		}
		public ClusterGroup(int size) {
			super();
			for (int i = 0; i < size; i++)
				add(new Cluster());
		}
	}
	
	@SuppressWarnings("serial")
	private class Cluster extends ArrayList<Integer> {
		public Cluster() {
			super();
		}
		public Cluster(Cluster that) {
			super(that);
			for (int i = 0; i < size(); i++)
				set(i, new Integer(get(i)));
		}
		public Cluster(int row) {
			super();
			add(row);
		}
		public Centroid computeCentroid() {
			try {
				Centroid centroid = new Centroid(UNKNOWN);	
				Matrix clusterMatrix = new Matrix(features, 0, 0, 0, features.cols());
				for (int row : this) 
					clusterMatrix.add(features, row, 0, 1);
				
				for (int col = 0; col < features.cols(); col++) {
					if (attributeIsNominal(col)) {
						centroid.set(col, clusterMatrix.mostCommonValue(col));
					}
					else {
						double sum = 0;
						int validRows = 0;
						for (int row = 0; row < clusterMatrix.rows(); row++) {
							if (clusterMatrix.get(row, col) == UNKNOWN) continue;
							sum += clusterMatrix.get(row, col);
							validRows++;
						}
						if (validRows == 0)
							centroid.set(col, UNKNOWN);
						else
							centroid.set(col, sum / validRows);
					}
				}
				return centroid;
			}
			catch (Exception e) { e.printStackTrace(); return null; }
		}
	}	

	@SuppressWarnings("serial")
	private class CentroidGroup extends ArrayList<Centroid> {
		public CentroidGroup() {
			super();
		}
	}

	@SuppressWarnings("serial")
	private class Centroid extends ArrayList<Double> { 
		public Centroid(double unknown) {
			super();
			for (int col = 0; col < features.cols(); col++)
				add(UNKNOWN);
		}
		public Centroid(double[] row) {
			super();
			for (double value : row)
				add(value);
		}
		public String toString() {
			String string = "";
			for (int index = 0; index < size(); index++) {
				if (get(index) == Double.MAX_VALUE) 
					string += "?";
				else if (attributeIsNominal(index)) {
					double val = get(index);
					int value = (int)val;
					string += features.attrValue(index, value);
				}
				else
					string += get(index);
				string += ",";
			}
			return string;
		}
	}	

	private Matrix features;
	private Matrix adjacencyMatrix;
	private final double UNKNOWN = Double.MAX_VALUE;
	private enum Link { SINGLE, COMPLETE }
	
}
